"""
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
"""



def search(nums, target):
    """
    使用二分查找算法在有序数组中查找目标值的下标

    Args:
        nums (list): 有序整数数组
        target (int): 目标值

    Returns:
        int: 目标值在数组中的下标，如果不存在则返回 -1
    """
    # 初始化左右指针
    left, right = 0, len(nums) - 1

    # 当左指针小于等于右指针时，继续查找
    while left <= right:
        # 计算中间位置
        mid = (left + right) // 2

        # 如果中间值等于目标值，返回下标
        if nums[mid] == target:
            return mid

        # 如果中间值小于目标值，更新左指针为中间位置加一
        elif nums[mid] < target:
            left = mid + 1

        # 如果中间值大于目标值，更新右指针为中间位置减一
        else:
            right = mid - 1

    # 如果循环结束还没有找到目标值，返回 -1
    return -1

if __name__ == '__main__':
    # 示例输入
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9

    # 调用 search 函数并打印结果
    print(search(nums, target))